Virtual memory is important in many modern, complex operating systems. Virtual memory is an imaginary memory area supported by some operating systems (for example, IBM's AIX™ operating system) in conjunction with the hardware. Virtual memory provides an alternate set of memory addresses. Programs use these virtual addresses rather than real addresses to store instructions and data. When the program is actually executed, the virtual addresses are converted into real memory addresses.
The purpose of virtual memory is to enlarge the address space, i.e., the set of addresses a program can utilize. For example, virtual memory might contain twice as many addresses as main memory. A program using all of virtual memory, therefore, would not be able to fit in main memory all at once. Nevertheless, the computer could execute such a program by copying into main memory those portions of the program needed at any given point during execution.
To facilitate copying virtual memory into real memory, the operating system divides virtual memory into pages, each of which contains a fixed number of addresses. Each page is stored on a disk until it is needed. When the page is needed, the operating system copies it from disk to main memory, translating the virtual addresses into real addresses.
In AIX™, virtual memory segments are partitioned into 4K (4096) byte units called pages and real memory is divided into 4K-byte page frames. The virtual memory manager (VMM) manages the allocation of page frames as well as resolving references to virtual-memory pages that are not currently in random access memory (RAM) (i.e., not currently stored in the paging space) or do not yet exist. To accomplish these tasks, the VMM maintains a “free list” of available page frames and uses a page-replacement algorithm to determine which virtual-memory pages that are currently in RAM will have their page frames reassigned to the free list (i.e., swapped out of the RAM).
Many VMMs try to anticipate when a program is sequentially reading a file from disk in order to pre-fetch pages so that subsequent pages will already be loaded into memory before being requested by the program. This anticipation performed by the VMM is often referred to as “Sequential-Access Read Ahead.”
In AIX™, the VMM tries to anticipate the future need for pages of a sequential file by detecting the pattern in which a program is accessing the file. When the program access two successive pages of a file, the VMM assumes that the program will continue to access the file sequentially. Consequently, the VMM schedules additional sequential reads of the file so that the file data is available to the program sooner than if the VMM waited to initiate the file I/O until the program requested the next page from the file.
In one example implementation of sequential-access read ahead, a first access of a file from the disk causes the first page (page 0) of the file to be read. At this point the virtual memory manager (VMM) makes no assumption about random or sequential file access. If the program accesses the first byte of the next page (page 1), with no intervening accesses to other pages of the file, then VMM concludes that the program is accessing sequentially. It schedules a number of extra pages (e.g., two extra pages). In this example, two additional pages (pages 2 and 3) are read. Thus, in this example a total of 3 pages are read as a result of the program's second read request. If the program accesses the first byte of the first page that has been read ahead (page 2), the VMM doubles the page-ahead value to 4 and schedules pages 4 through 7 to be read from the file. If the program accesses the first byte of the first page that has been read ahead (page 4), the VMM again doubles the page-ahead value to 8 and schedules pages 8 through 15 to be read. This doubling continues until the amount of data being read reaches a predetermined maximum or until the end of the file is reached.
A challenge, however, to pre-fetching large numbers of sequentially-accessed pages is that the RAM memory can sometimes become constrained. When memory becomes constrained, the VMM determines which virtual-memory pages that are currently in RAM will be subjected to the page replacement function, which reassigns their page frames to the free list and swaps them out of the RAM.
When the page replacement function of the VMM steals one or more of the read-ahead pages before the application reads them, the application must wait for a physical I/O to the disk to complete for one or more of its pages, rather than just read the pre-fetched pages from memory.